#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;
/*
 *面试题 10.03. 搜索旋转数组
提示
中等
120
相关企业
搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。

示例1:

 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 输出: 8（元素5在该数组中的索引）
示例2:
 输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 输出：-1 （没有找到）
提示:
arr 长度范围在[1, 1000000]之间
 * */
//尝试使用二分法解决
int search(vector<int> &arr, int target) {

    // ----
    int low = 0;
    int high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[low] == target)
            return low;

        if (arr[mid] == target)
            return mid;
        if (arr[high] == target)
            return high;


        if (mid - 1 > 0 && mid + 1 < arr.size() - 1 && arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
            low++;
            continue;
        }

        //说明区间递减 且在他的下面部分
        if (mid - 1 > 0 && arr[mid] > target && arr[mid - 1] > arr[mid]) {
            low = mid + 1;
        } else {
            low++;
        }


    }


    return -1;
}


//怎么说这个 一个有序数组反转一次跟反转多次是一个道理
// 意思就是一个代码就行了
int search1(vector<int> &nums, int target) {
    int low = 0;
    int high = nums.size() - 1;

    while (low <= high) {
        //这样就通过了 要不可能会找到不是最优的数字 todo 你说如果从左边开始检测会不会好点
        if (nums[low] == target) {
            while (low - 1 >= 0 && nums[low - 1] == target)
                low--;

            return low;
        }
        if (nums[high] == target) {
            while (high - 1 >= 0 && nums[high - 1] == target)
                high--;

            return high;
        }

        int mid = low + (high - low) / 2;

        if (nums[mid] == target) {

            while (mid - 1 >= 0 && nums[mid - 1] == target)
                mid--;
            return mid;
        }

            //2,5,6,0,0,1,2
            //说明右边这有序
        else if (nums[mid] < nums[high]) {
            //说明可能在右半部分
            if (nums[mid] < target && nums[high] >= target)
                low = mid + 1;
            else
                high = mid - 1;//很明显mid不是-1得

            //说明左半部分有序
        } else if (nums[mid] > nums[high]) {
            if (nums[mid] > target && nums[low] <= target) {
                //说明在区间里面
                high = mid - 1;
            } else
                low = mid + 1;
        } else {
            high--;
            //这里不能low++ 这边是右侧去重 因为判断的都是mid值和high 比较的所以得右边去重high--;
        }


    }

    return -1;

}